package com.sun.javaalgorithm.day04;

import java.util.LinkedList;

/**
 * @version 1.0
 * @Package: com.sun.javaalgorithm.day04
 * @ClassName: HanoiTower
 * @Author: sgq
 * @Date: 2024/4/17 10:59
 * @Description: 汉诺塔问题
 * <p>
 * <p>
 * 简单来讲，汉诺塔问题是这样的：
 * 给定三根柱子，记为 A,B,C ，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n-1 ，且上面的盘子一定比下面的盘子小。
 * 问：将 A 柱上的盘子经由 B 柱移动到 C柱最少需要多少次？
 * 移动时应注意：① 一次只能移动一个盘子 ②大的盘子不能压在小盘子上
 */
public class HanoiTower {

    private static LinkedList<Integer> a = new LinkedList<>();
    private static LinkedList<Integer> b = new LinkedList<>();
    private static LinkedList<Integer> c = new LinkedList<>();

    /**
     * 初始化a柱
     *
     * @param n
     */
    private static void init(int n) {
        for (int i = n; i > 0; i--) {
            a.addLast(i);
        }
    }

    /**
     * 打印
     */
    private static void print() {
        System.out.println("a=" + a);
        System.out.println("b=" + b);
        System.out.println("c=" + c);
        System.out.println("------------------");
    }

    /**
     * 移动核心方法
     */
    private static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b);
        c.addLast(a.removeLast());
        print();
        move(n - 1, b, a, c);
    }

    public static void main(String[] args) {
        init(3);
        print();
        move(3, a, b, c);
    }

}
